Vytvořující funkce (posloupnost)

Vytvořující (též generující) funkce posloupnosti $\{a_{i}\}$ je mocninná řada, která v sobě obsahuje informaci o dané posloupnosti. Vytvořující funkce tedy umožňuje popsat posloupnost a pracovat s ní prostřednictvím funkce, která v sobě obsahuje veškeré informace o dané posloupnosti, a naopak otázky týkající se funkcí převádět na zkoumání posloupností. Teorie vytvořujících funkcí má však svoje omezení: Ne každé funkci odpovídá nějaká mocninná řada a ne každá mocninná řada konverguje kdekoli kromě nuly (což ovšem v zásadě nebrání s ní pracovat jako s vytvořující funkcí, pokud nepotřebujeme využít analytické vlastnosti jí definované funkce, ale chápeme ji jen jako tzv. formální mocninnou řadu).

Důležitými aplikacemi teorie vytvořujících funkcí jsou momentová vytvořující funkce v teorii pravděpodobnosti, která mimo jiné umožňuje odvodit rozdělení pravděpodobnosti součtu dvou nezávislých náhodných veličin se známými rozděleními, a příbuzná pravděpodobnostní vytvořující funkce. S pomocí vytvořujících funkcí lze také řešit různé kombinatorické úlohy.

Definice

Obyčejnou vytvořující funkci posloupnosti $(a_{0},a_{1},a_{2},...)$ zapíšeme jako

$a(x)=a_{0}+a_{1}x+a_{2}x^{2}+...=\sum _{i=0}^{\infty }a_{i}x^{i}$

Jedná o tzv. otevřený tvar vytvořující funkce. Poznáme ho tak, že je v něm nekonečný součet (což se nám nemusí příliš líbit). Proto často chceme nalézt tzv. uzavřený tvar, ve kterém se nekonečný součet nevyskytuje.

Vysvětlení na praktické ukázce

Mějme např. posloupnost

$(1,1,1,1,1,...)$

Pak její vytvořující funkci lze zapsat (na intervalu, ve kterém tato řada konverguje) jako:

$a(x)=1+1x+1x^{2}+...$

Uzavřený tvar této funkce lze snadno odvodit z obecného vztahu pro součet geometrické posloupnosti:

${1} \over {1-x}$

Tyto dva tvary spolu souvisí tak, že když do nich doplníme za $x$ libovolné reálné číslo z intervalu (-1,1) tzn. |x|<1, pro které uvedená mocninná řada konverguje, vyjde nám v obou tvarech vždy naprosto stejný výsledek.

Například doplníme $x=0.5$, pak nám vyjde součet otevřeného tvaru vytvořující funkce:

$a(0.5)=1+0.5+0.5^{2}+0.5^{3}+...=1+0.5+0.25+0.125+...=2$

A pro stejné $x=0.5$ vyjde uzavřený tvar taktéž:

${{1} \over {1-0.5}}=2$

Vytvořující funkci této jednoduché posloupnosti lze dále považovat za klíčovou pro odvození uzavřených tvarů složitějších posloupností.

Například derivací řady $a(x)=1+1x+1x^{2}+1x^{3}+...$ získáme řadu $b(x)=0+1+2x+3x^{2}+...$

Pokud tedy zderivujeme uzavřený tvar $a(x)$ dostaneme

$a(x)'=b(x)={{1} \over {(1-x)^{2}}}$

Tato nová odvozená funkce představuje posloupnost $(1,2,3,4,5,...)$

Podobnými úpravami lze postupně odvodit vytvořující funkce i pro vybrané posloupnosti (viz tabulka níže).

Výpočet koeficientu posloupnosti z vytvořující funkce

Máme-li vytvořující funkci ve tvaru ${1} \over {(1-x)^{n}}$, vypočítáme požadovaný koeficient $a_{k}$ následovně:

$a_{k}=C_{n-1+k}^{n-1}={\begin{pmatrix}n-1+k\\n-1\end{pmatrix}}$

Nebo lze pro $(1+x)^{-n}$ použít tento vzoreček

$a_{k}=C_{-n}^{k}=(-1)^{k}*C_{n+k-1}^{k}$

Příklad

Hledáme koeficient $a_{8}$ u vytv. fce $(1-x)^{-3}={{1} \over {(1-x)^{3}}}$:

$a_{8}=C_{3-1+8}^{3-1}=C_{10}^{2}=45$

Poznámka: Výpočet hodnoty koeficientu u tohoto typu vytvořující funkce vychází ze zobecněné binomické věty.

Vybrané posloupnosti a jejich vytvořující funkce

posloupnost	vytv. fce pro $x\in (-1;1)$
$\left(1,1,1,1,...\right)$	${1} \over {1-x}$
$\left(1,-1,1,-1,...\right)$	${1} \over {1+x}$
$\left(1,0,1,0,...\right)$	${1} \over {1-x^{2}}$
$\left(1,0,...,0,1,0,...,0,1,0,...\right)$	${1} \over {1-x^{n}}$
$\left(1,2,3,4,5,...\right)$	${1} \over {(1-x)^{2}}$
$\left(1,k,k^{2},k^{3},k^{4},...\right)$	${1} \over {1-kx}$
$\left(1,{\begin{pmatrix}k\\1\end{pmatrix}},{\begin{pmatrix}k\\2\end{pmatrix}},{\begin{pmatrix}k\\3\end{pmatrix}},{\begin{pmatrix}k\\4\end{pmatrix}},...\right)$	$\left(1+x\right)^{k}$
$\left(1,k,{\begin{pmatrix}k-1\\k-1\end{pmatrix}},{\begin{pmatrix}k\\k-1\end{pmatrix}},{\begin{pmatrix}k+1\\k-1\end{pmatrix}},...\right)$	${1} \over {\left(1-x\right)^{k}}$
$\left(0,1,{{1} \over {2}},{{1} \over {3}},{{1} \over {4}},...\right)$	$\ln {1 \over {1-x}}$
$\left(0,1,-{{1} \over {2}},{{1} \over {3}},-{{1} \over {4}},...\right)$	$\ln \left(1+x\right)$
$\left(1,1,{{1} \over {2}},{{1} \over {6}},{{1} \over {24}},{{1} \over {120}},...,{{1} \over {k!}},...\right)$	$e^{x}$

Odkazy

Externí odkazy

• WILF, Herbert S. Generatingfunctionology. 3. vyd. Wellesley, Mass.: A. K. Peters, 2006. x, 245 pages s. Dostupné online. ISBN 1-56881-279-5, ISBN 978-1-56881-279-3. OCLC 62302522 

Související články

• Posloupnost
• Momentová vytvořující funkce

Externí odkazy

• Vytvořující funkce ve studijních textech semináře MKS MFF UK

Autoritní data	BNF: cb12259609r (data) GND: 4152979-0 LCCN: sh85053815 NLI: 987007562699905171